1

2

3

4

5

6

FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径

    如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。 这样的话时间复杂度为EV^2

    如果是稀疏图，则近似于V^3

    但是如果是密集图，则时间复杂度会近似达到V^4，这种情况需要优化，这里FloydWarshall通过动态规划进行优化

    ，并且使用邻接矩阵来表示图。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

package org.loda.graph;

import java.math.BigDecimal;

import java.math.RoundingMode;

import org.loda.util.In;

/**

 *

 * @ClassName: FloydWarshall

 * @Description: 求一个图中任意两点之间的最短路径

 *

 *        FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径

 *

 *        如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。 这样的话时间复杂度为EV^2

 *        如果是稀疏图，则近似于V^3

 *        但是如果是密集图，则时间复杂度会近似达到V^4，这种情况需要优化，这里FloydWarshall通过动态规划进行优化

 *        ，并且使用邻接矩阵来表示图。

 *         d(i,j); if m=0

 *        D(i,j,m)={

 *         min(D(i,m,m-1)+D(m,j,m-1),D(i,j,m-1)); if m!=0

 * @author minjun

 * @date 2015年6月1日 上午9:39:42

 *

 */

public class FloydWarshall {

 private double[][] d;

 private int[][] prev;

 private int v;

 private boolean negativeCycle;

 public FloydWarshall(int v) {

 this.v = v;

 d = new double[v][v];

 prev = new int[v][v];

 // 默认设置所有节点都不可达，而自己到自己是可达并且距离为0.0

 for (int i = 0; i < v; i++) {

  for (int j = 0; j < v; j++) {

  d[i][j] = Double.POSITIVE_INFINITY;

  prev[i][j] = -1;

  if(i==j){

   d[i][j] = 0;

  }

  }

 }

 }

 /**

 *

 * @Title: findShortestPath

 * @Description: 查询最短路径

 * @param 设定文件

 * @return void 返回类型

 * @throws

 */

 public void findShortestPath() {

 //查找最短路径

 for (int k = 0; k < v; k++) {

  //将每个k值考虑成i->j路径中的一个中间点

  for (int i = 0; i < v; i++) {

  for (int j = 0; j < v; j++) {

   //如果存在使得权重和更小的中间值k，就更新最短路径为经过k的路径

   if (d[i][j] > d[i][k] + d[k][j]) {

   d[i][j] = d[i][k] + d[k][j];

   prev[i][j]=k;

   }

  }

  }

 }

 //四舍五入距离

 for (int i = 0; i < v; i++) {

  for (int j = 0; j < v; j++) {

  d[i][j] = new BigDecimal(d[i][j]).setScale(2,

   RoundingMode.HALF_UP).doubleValue();

  }

 }

 //检测负权重环的方式很简单，就是判断所有i->i的距离d[i][i]，如果存在小于0的，表示这个i->i的环路的权重和形成了一个负值，也就是存在这个负权重

 //在之前的其他最短路径算法中，无法通过这个方法来检测负环，因为之前路径距离都是保存在一个一维数组中，相等于只能检测d[0][0]，无法检测每个d[i][i]

 for(int i=0;i<v;i++){

  if(d[i][i]<0)

  negativeCycle=true;

 }

 }

 /**

 *

 * @Title: hasNegativeCycle

 * @Description: 是否拥有负权重环

 * @param @return 设定文件

 * @return boolean 返回类型

 * @throws

 */

 public boolean hasNegativeCycle() {

 return negativeCycle;

 }

 /**

 *

 * @Title: distTo

 * @Description: a->b最短路径的距离

 * @param @param a

 * @param @param b

 * @param @return 设定文件

 * @return double 返回类型

 * @throws

 */

 public double distTo(int a, int b) {

 if (hasNegativeCycle())

  throw new RuntimeException("有负权重环，不存在最短路径");

 return d[a][b];

 }

 /**

 *

 * @Title: printShortestPath

 * @Description: 打印a->b最短路径

 * @param @return 设定文件

 * @return Iterable<Integer> 返回类型

 * @throws

 */

 public boolean printShortestPath(int a,int b){

 if (hasNegativeCycle()){

  System.out.print("有负权重环，不存在最短路径");

 }else if(a==b)

  System.out.println(a+"->"+b);

 else{

  System.out.print(a+"->");

  path(a,b);

  System.out.print(b);

 }

 return true;

 }

 private void path(int a, int b) {

 int k=prev[a][b];

 if(k==-1){

  return;

 }

 path(a,k);

 System.out.print(k+"->");

 path(k,b);

 }

 /**

 *

 * @Title: addEdge

 * @Description: 添加边

 * @param @param a

 * @param @param b

 * @param @param w 设定文件

 * @return void 返回类型

 * @throws

 */

 public void addEdge(int a, int b, double w) {

 d[a][b] = w;

 }

 public static void main(String[] args) {

 // 不含负权重环的文本数据

 String text1 = "F:\\算法\\attach\\tinyEWDn.txt";

 // 含有负权重环的文本数据

 String text2 = "F:\\算法\\attach\\tinyEWDnc.txt";

 In in = new In(text1);

 int n = in.readInt();

 FloydWarshall f = new FloydWarshall(n);

 int e = in.readInt();

 for (int i = 0; i < e; i++) {

  f.addEdge(in.readInt(), in.readInt(), in.readDouble());

 }

 f.findShortestPath();

 int s = 0;

 for (int i = 0; i < n; i++) {

  System.out.println(s + "到" + i + "的距离为:" + f.distTo(s, i));

  f.printShortestPath(s, i);

  System.out.println();

 }

 }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

0到0的距离为:0.0

0->0

0到1的距离为:0.93

0->2->7->3->6->4->5->1

0到2的距离为:0.26

0->2

0到3的距离为:0.99

0->2->7->3

0到4的距离为:0.26

0->2->7->3->6->4

0到5的距离为:0.61

0->2->7->3->6->4->5

0到6的距离为:1.51

0->2->7->3->6

0到7的距离为:0.6

0->2->7